Генеративные методы классификации

Два подхода к классификации

До этого момента мы рассматривали классификацию преимущественно с дискриминативной точки зрения. Дискриминативные модели (discriminative models) стремятся напрямую найти границы между классами, настраивая дискриминантные функции $\{g_y(\boldsymbol{x})\}_y$ или оценивая условную вероятность $p(y|\boldsymbol{x})$, проводя разделяющую поверхность в пространстве признаков.

Однако существует принципиально иной путь — генеративные модели (generative models), представляющие собой разновидность вероятностых моделей, в которых мы

• явно моделируем плотность распределения признаков для каждого класса $p(\boldsymbol{x}|y=c)$;

• учитываем, насколько часто в целом тот или иной класс встречается через его априорную вероятность $p(y=c)$.

В генеративном подходе настраиваемыми параметрами выступают априорные распределения классов $p(y=c)$ и параметры модельного распределения $p(\boldsymbol{x}|y=c)$, которые оцениваются методом максимального правдоподобия.

Метод называется генеративным, потому что, построив такую модель, мы можем генерировать новые объекты $\boldsymbol{x}$ по следующей процедуре:

1. сэмплируем класс объекта $y\sim\text{Categorical}\{p(y=1,...y=C)\}$;

2. сэмплируем сам объект из модельного распределения $\boldsymbol{x}\sim p(\boldsymbol{x}|y=c)$.

Правило построения прогнозов

Генеративные модели, будучи вероятностными моделями, прогнозируют класс по принципу максимальной вероятности:

$$\hat{y} = \arg\max_c p(y=c|\boldsymbol{x})$$

Однако поскольку в них явно делаются предположения о распределении объектов в каждом классе, эти вероятности эквивалентно переписываются по формуле Байеса:

$$\hat{y} = \arg\max_c \frac{p(\boldsymbol{x}|y=c) p(y=c)}{p(\boldsymbol{x})}$$

Так как знаменатель $P(\boldsymbol{x})$ одинаков для всех классов, он не влияет на результат, и его можно отбросить:

$$\hat{y} = \arg\max_c \{ P(\boldsymbol{x}|y=c) p(y=c) \}$$

Для удобства вычислений максимизируют не сами величины, а их логарифмы. Поскольку логарифм - монотонно возрастающая функция, это также не влияет на прогноз:

$$\hat{y} = \arg\max_c \{ P(\boldsymbol{x}|y=c) p(y=c) \}$$

Таким образом, дискриминантными функциями в генеративных моделях являются

$$g_c(\boldsymbol{x}) = \ln p(\boldsymbol{x}|y=c) + \ln p(y=c), \quad c=1,2,...C$$

Настройка генеративных моделей

Для обучения генеративной модели необходимо оценить набор её параметров $\boldsymbol{\Theta}$. В него входят априорные вероятности классов $\pi_c = p(y=c)$ и параметры плотностей распределения объектов внутри каждого класса $\boldsymbol{\theta}_c$ (например, вектора средних и ковариационные матрицы):

$$\boldsymbol{\Theta} = \left\{ \{\pi_c\}_{c=1}^C, \{\boldsymbol{\theta}_c\}_{c=1}^C \right\}$$

Настройка параметров осуществляется через максимизацию логарифма правдоподобия совместного распределения признаков и меток классов обучающей выборки. Данный подход называется метод максимального правдоподобия (Maximum Likelihood Estimation, MLE). Оптимизационная задача в общем виде записывается следующим образом:

$$\mathcal{L}(\boldsymbol{\Theta}) = \sum_{n=1}^N \ln p(\boldsymbol{x}_n, y_n | \boldsymbol{\Theta}) \to \max_{\boldsymbol{\Theta}}$$

Используя определение совместной вероятности $p(\boldsymbol{x}_n, y_n) = p(\boldsymbol{x}_n | y_n, \boldsymbol{\theta}_{y_n}) \cdot \pi_{y_n}$, логарифм правдоподобия можно разложить на две составляющие:

$$\mathcal{L}(\boldsymbol{\Theta}) = \sum_{n=1}^N \ln p(\boldsymbol{x}_n | y_n, \boldsymbol{\theta}_{y_n}) + \sum_{n=1}^N \ln \pi_{y_n} \to \max_{\{\pi_c\}, \{\boldsymbol{\theta}_c\}}$$

При этом на априорные вероятности накладывается ограничение $\sum_{c=1}^C \pi_c = 1$. Решение этой задачи для $\pi_c$ даёт естественную оценку доли объектов каждого класса в выборке:

$$\pi_c = \frac{N_c}{N},$$

где $N_c$ — количество объектов класса $c$.

Независимость настройки

Важной особенностью генеративного подхода является то, что параметры каждого класса $\boldsymbol{\theta}_c$ настраиваются независимо друг от друга. Для каждого класса $c$ решается своя подзадача оптимизации:

$$\sum_{n: y_n=c} \ln p(\boldsymbol{x}_n | \boldsymbol{\theta}_c) \to \max_{\boldsymbol{\theta}_c}$$

Параметры правдоподобия

Выбор конкретного вида распределения $p(\boldsymbol{x} | y=c, \boldsymbol{\theta}_c)$ определяет сложность и гибкость модели.

• Если признаки внутри класса распределены по многомерному нормальному закону, то параметрами $\boldsymbol{\theta}_c$ будут выступать вектор среднего $\boldsymbol{\mu}_c$ и ковариационная матрица $\Sigma_c$.

• Если признаки считаются независимыми при условии класса, мы получаем наивный байесовский классификатор (Naive Bayes), где параметры оцениваются для каждого признака $\boldsymbol{x}^i$ отдельно, что упрощает обучение модели.

Генеративные модели не требуют итеративных методов оптимизации (таких как градиентный спуск), если для выбранного распределения существуют аналитические формулы оценок максимального правдоподобия. Это делает их обучение чрезвычайно быстрым.

Сравнение подходов

Выбор между генеративным и дискриминативным подходами зависит от объема данных и решаемой задачи.

Преимущества генеративных моделей

1. Работа с пропусками: они позволяют классифицировать объекты, у которых часть признаков $\boldsymbol{x}^i$ отсутствует, путем интегрирования по распределению пропущенных признаков.
2. Детекция аномалий: если значение $p(\boldsymbol{x})$ очень мало для всех классов, мы можем сделать вывод, что объект является выбросом (outlier).
3. Эффективность на малых данных: они сходятся к лучшему решению, чем дискриминативные, если предположение о виде распределения $p(\boldsymbol{x}|y=c)$ оказалось близким к истинному.

Риск неверной модели

Если наше предположение о виде распределения $p(\boldsymbol{x}|y=c)$ окажется далёким от истинного, генеративная модель будет давать сильно смещённый прогноз даже для больших выборок!

Преимущества дискриминативных моделей

1. Качество прогноза: они обычно показывают лучшую точность на больших обучающих выборках, так как фокусируются на границе классов, а не на их внутреннем устройстве.
2. Гибкость: им не требуется делать сильных предположений о законе распределения признаков, что делает их более гибкими в настройке.